package collections;

import util.Tracer;

public class BinarySearchTree <T extends Comparable<T>>{
	BinarySearchTreeNode<T> root;
	
	public BinarySearchTreeNode<T> search(T k)
	{
		BinarySearchTreeNode<T> node = root;

		int ret;
		while(node != null && (ret = k.compareTo(node.getKey())) != 0)
		{
			if(ret < 0)
				node = node.getLeftChild();
			else
				node = node.getRightChild();
		}
		
		return node;
	}
	
	public void inOrderWalk()
	{
		inOrderWalk(root);
	}
	
	private void inOrderWalk(BinarySearchTreeNode<T> node)
	{
		if(node == null) return;

		inOrderWalk(node.getLeftChild());
		Tracer.trace(node.getKey());
		inOrderWalk(node.getRightChild());
	}
	
	public void inOrderWalkWithStack()
	{
		inOrderWalkWithStack(root);
	}
	
	private void inOrderWalkWithStack(BinarySearchTreeNode<T> node)
	{
		if(node == null) return;

		SinglyLinkedListStack<BinarySearchTreeNode<T>> stack = new SinglyLinkedListStack<BinarySearchTreeNode<T>>();

		while(node != null || !stack.isEmpty())
		{
			if(node != null)
			{
				BinarySearchTreeNode<T> descendant = node.getLeftChild();
				if(descendant == null)
					Tracer.trace(node.getKey());
				else
					stack.push(node);

				node = descendant;
			}
			else
			{
				BinarySearchTreeNode<T>  tmp = stack.pop();
				Tracer.trace(tmp.getKey());

				node = tmp.getRightChild();;
			}
		}
	}
	
	public void inOrderWalkWithoutStack()
	{
		inOrderWalkWithoutStack(root);
	}
	
	private void inOrderWalkWithoutStack(BinarySearchTreeNode<T> node)
	{
		BinarySearchTreeNode<T> tmp = minimum(node);
		while(tmp != null)
		{
			Tracer.trace(tmp.getKey());
			tmp = successor(tmp);
		}
	}
	
	public BinarySearchTreeNode<T> minimum()
	{
		return minimum(root);
	}
	
	public void insert(BinarySearchTreeNode<T> node)
	{
		BinarySearchTreeNode<T> parent = null;
		BinarySearchTreeNode<T> ref = root;

		while(ref != null)
		{
			parent = ref;

			if(node.getKey().compareTo(ref.getKey()) < 0)
			{
				ref = ref.getLeftChild();
			}
			else
			{
				ref = ref.getRightChild();
			}
		}
		
		if(parent == null)
		{
			root = node;
		}
		else if(node.getKey().compareTo(parent.getKey()) < 0)
		{
			parent.setLeftChild(node);
		}
		else
		{
			parent.setRightChild(node);
		}
	}
	
	public void delete(BinarySearchTreeNode<T> node)
	{
		BinarySearchTreeNode<T> right = node.getRightChild();
		BinarySearchTreeNode<T> left = node.getLeftChild();
		
		if(left == null)
		{
			transplant(node, right);
		}
		else if(right == null)
		{
			transplant(node, left);
		}
		else
		{
			BinarySearchTreeNode<T> minNode = minimum(right);
			if(minNode.getParent() != node)
			{
				transplant(minNode, minNode.getRightChild());
				minNode.setRightChild(node.getRightChild());
			}

			transplant(node, minNode);
			minNode.setLeftChild(node.getLeftChild());
		}
	}
	
	private void transplant(BinarySearchTreeNode<T> node1, BinarySearchTreeNode<T> node2)
	{
		BinarySearchTreeNode<T> parent = node1.getParent();
		
		if(parent == null)
			root = node2;
		else if(node1 == parent.getLeftChild())
			parent.setLeftChild(node2);
		else
			parent.setRightChild(node2);
	}
	
	private BinarySearchTreeNode<T> minimum(BinarySearchTreeNode<T> node)
	{
		if(node == null)
			return null;

		BinarySearchTreeNode<T> child;
		while((child = node.getLeftChild()) != null)
		{
			node = child;
		}
		
		return node;
	}

	public BinarySearchTreeNode<T> maximum()
	{
		return maximum(root);
	}
	
	private BinarySearchTreeNode<T> maximum(BinarySearchTreeNode<T> node)
	{
		if(node == null)
			return null;

		BinarySearchTreeNode<T> child;
		while((child = node.getRightChild()) != null)
		{
			node = child;
		}
		
		return node;
	}
	
	public BinarySearchTreeNode<T> successor(BinarySearchTreeNode<T> node)
	{
		BinarySearchTreeNode<T> next = node.getRightChild();
		if(next != null)
			return minimum(next);

		BinarySearchTreeNode<T> ancestor = node.getParent();
		while(ancestor != null && node == ancestor.getRightChild())
		{
			node = ancestor;
			ancestor = node.getParent();
		}
		
		return ancestor;
	}
	
	public BinarySearchTreeNode<T> predecessor(BinarySearchTreeNode<T> node)
	{
		BinarySearchTreeNode<T> next = node.getLeftChild();
		if(next != null)
			return maximum(next);
		
		BinarySearchTreeNode<T> ancestor = node.getParent();
		while(ancestor != null && node == ancestor.getLeftChild())
		{
			node = ancestor;
			ancestor = node.getParent();
		}
		
		return ancestor;
	}
	
	public static void main(String[] args) {
		BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
		tree.insert(new BinarySearchTreeNode<Integer>(8));
		tree.insert(new BinarySearchTreeNode<Integer>(4));
		tree.insert(new BinarySearchTreeNode<Integer>(12));
		tree.insert(new BinarySearchTreeNode<Integer>(2));
		tree.insert(new BinarySearchTreeNode<Integer>(6));
		tree.insert(new BinarySearchTreeNode<Integer>(10));
		tree.insert(new BinarySearchTreeNode<Integer>(14));
		tree.insert(new BinarySearchTreeNode<Integer>(1));
		tree.insert(new BinarySearchTreeNode<Integer>(3));
		tree.insert(new BinarySearchTreeNode<Integer>(5));
		tree.insert(new BinarySearchTreeNode<Integer>(7));
		tree.insert(new BinarySearchTreeNode<Integer>(9));
		tree.insert(new BinarySearchTreeNode<Integer>(11));
		tree.insert(new BinarySearchTreeNode<Integer>(13));
		tree.insert(new BinarySearchTreeNode<Integer>(15));


		tree.delete(tree.search(9));
		tree.inOrderWalkWithoutStack();
	}
}
